import java.util.ArrayList;
import java.util.List;

public class demo1 {
    List<List<Integer>>list;
    List<Integer>path;
    int n=0;
    public List<List<Integer>> combinationSum(int[] candidates, int target) {
        list=new ArrayList<>();
        path=new ArrayList<>();
        n=target;
        dfs(candidates,0,0);
        return list;
    }
    public void dfs(int[]candidates,int sum,int pos){
        if(sum==n){
            list.add(new ArrayList<>(path));
            return;
        }
        if(sum>n)return;//递归出口 不设置这个sum>n的值将死循环
        //if(pos==candidates.length||sum>n)return;
        for(int i=pos;i<candidates.length;i++){
            sum=sum+candidates[i];
            path.add(candidates[i]);
            dfs(candidates,sum,i);
            sum-=candidates[i];//回溯关键：回溯时减去，恢复sum原值
            path.remove(path.size()-1);
        }
    }
}
